GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Primfaktorzerlegung</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading">Primfaktorzerlegung</h1>

</header>

</div>

<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">Die Primfaktorzerlegung ist die Darstellung einer positiven <a href="Nat%C3%BCrliche_Zahl" title="Natürliche Zahl">natürlichen Zahl</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n\in \mathbb {N} ^{+}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n\in \mathbb {N} ^{+}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3153bd419225b1dd1067de6dc35ef104c83aab2b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.424ex; height:2.509ex;" alt="{\displaystyle n\in \mathbb {N} ^{+}}" loading="lazy"> als <a href="Produkt_(Mathematik)" title="Produkt (Mathematik)">Produkt</a> aus <a href="Primzahl" title="Primzahl">Primzahlen</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\in \mathbb {P} ,}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\in \mathbb {P} ,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cf87c28b12c67c97dcc87c9084cccfa1468d3f1d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:6.167ex; height:2.509ex;" alt="{\displaystyle p\in \mathbb {P} ,}" loading="lazy"> die dann als Primfaktoren von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> bezeichnet werden. Diese Darstellung ist eindeutig (bis auf die Reihenfolge der Faktoren; es ist eine <a href="Multimenge" title="Multimenge">Multimenge</a>) und zählt zu den grundlegenden und klassischen Werkzeugen der <a href="Zahlentheorie" title="Zahlentheorie">Zahlentheorie</a>. Sie ist Gegenstand des <a href="#Fundamentalsatz_der_Arithmetik">Fundamentalsatzes der Arithmetik</a>. Es ist bisher kein <a href="Effizienz_(Informatik)" title="Effizienz (Informatik)">effizientes</a> <a href="Faktorisierungsverfahren" title="Faktorisierungsverfahren">Faktorisierungsverfahren</a> bekannt, um die Primfaktorzerlegung einer beliebigen Zahl zu erhalten.

<th rowspan="2">Zahl

</th>

<th colspan="3">Faktoren

</th></tr>

<th>An- zahl

</th>

<th>einzeln

</th>

<th>kano- nisch

</th></tr>

<tr>

<td>0

</td>

<td>–

</td></tr>

<tr>

<td>1

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/425a2d11274fd2224c4c4db47edd305a8f34bac1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}}" loading="lazy"></td>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/425a2d11274fd2224c4c4db47edd305a8f34bac1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}}" loading="lazy">

</td></tr>

<tr>

<td>1

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkgreen}3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0e4984f153b838e3209eba29c996a274697f2bd7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle {\color {darkgreen}3}}" loading="lazy"></td>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkgreen}3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0e4984f153b838e3209eba29c996a274697f2bd7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle {\color {darkgreen}3}}" loading="lazy">

</td></tr>

<tr>

<td>2

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {blue}2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e3182e6c8985fdd1c8fc45ca34aba78412ce6897.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {blue}2}}" loading="lazy"></td>

<msup>

</mstyle>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e84d8e11044d3a0f648cf9b10cdc03033b6dc6fc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.217ex; height:2.676ex;" alt="{\displaystyle {\color {blue}2}^{2}}" loading="lazy">

</td></tr>

<tr>

<td>1

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkred}5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0c666f1f54dc7112d146d9687677b16aaf3e96ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle {\color {darkred}5}}" loading="lazy"></td>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkred}5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0c666f1f54dc7112d146d9687677b16aaf3e96ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle {\color {darkred}5}}" loading="lazy">

</td></tr>

<tr>

<td>2

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {darkgreen}3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/32cede8d2ca6331e3b46cba4775075415b241595.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {darkgreen}3}}" loading="lazy"></td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {darkgreen}3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/32cede8d2ca6331e3b46cba4775075415b241595.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {darkgreen}3}}" loading="lazy">

</td></tr>

<tr>

<td>1

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkgray}7}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6c2df47b84312654d7a4009840984947bc8cec1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle {\color {darkgray}7}}" loading="lazy"></td>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkgray}7}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6c2df47b84312654d7a4009840984947bc8cec1f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle {\color {darkgray}7}}" loading="lazy">

</td></tr>

<tr>

<td>3

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {blue}2}\cdot {\color {blue}2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/efcf111180556dd37070ddbdc83c3761b34b732b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.846ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {blue}2}\cdot {\color {blue}2}}" loading="lazy"></td>

<msup>

</mstyle>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}^{3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/17e9b0a8badfe1102f8603823a4599807119a068.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.217ex; height:2.676ex;" alt="{\displaystyle {\color {blue}2}^{3}}" loading="lazy">

</td></tr>

<tr>

<td>2

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkgreen}3}\cdot {\color {darkgreen}3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fd969b4dd3d2eaeabc1848aefe770bf25bb9ee67.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {darkgreen}3}\cdot {\color {darkgreen}3}}" loading="lazy"></td>

<msup>

</mstyle>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkgreen}3}^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9b0b4438c96adaf5257077c55373fc4fd0632a8e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.217ex; height:2.676ex;" alt="{\displaystyle {\color {darkgreen}3}^{2}}" loading="lazy">

</td></tr>

<tr>

<td>2

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {darkred}5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1908ab0962df0e94378dd9872cb5bab673db663.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {darkred}5}}" loading="lazy"></td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {darkred}5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c1908ab0962df0e94378dd9872cb5bab673db663.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {darkred}5}}" loading="lazy">

</td></tr>

<tr>

<td>1

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 11}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da6aabe7c6af49fe640b2d401cb2dbe909bb7475.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 11}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 11}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da6aabe7c6af49fe640b2d401cb2dbe909bb7475.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 11}" loading="lazy">

</td></tr>

<tr>

<td>3

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {blue}2}\cdot {\color {darkgreen}3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f7bc58742ba3cc8a2e54de6103d057fdaa911a9c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.846ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {blue}2}\cdot {\color {darkgreen}3}}" loading="lazy"></td>

<msup>

</mstyle>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}^{2}\cdot {\color {darkgreen}3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/613d43c04305fe14ce6d3a8df2489ed5c089f9e8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.058ex; height:2.676ex;" alt="{\displaystyle {\color {blue}2}^{2}\cdot {\color {darkgreen}3}}" loading="lazy">

</td></tr>

<tr>

<td>1

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 13}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d478c234d544278fb494e9610b7b3310567302b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 13}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 13}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d478c234d544278fb494e9610b7b3310567302b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 13}" loading="lazy">

</td></tr>

<tr>

<td>2

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {darkgray}7}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/16827ed9800ac94d87f95ef6955da480da030aba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {darkgray}7}}" loading="lazy"></td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {darkgray}7}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/16827ed9800ac94d87f95ef6955da480da030aba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {darkgray}7}}" loading="lazy">

</td></tr>

<tr>

<td>2

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkgreen}3}\cdot {\color {darkred}5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba1c6b743927dac731b13de7b526d52c1f549b08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {darkgreen}3}\cdot {\color {darkred}5}}" loading="lazy"></td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkgreen}3}\cdot {\color {darkred}5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba1c6b743927dac731b13de7b526d52c1f549b08.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {darkgreen}3}\cdot {\color {darkred}5}}" loading="lazy">

</td></tr>

<tr>

<td>4

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {blue}2}\cdot {\color {blue}2}\cdot {\color {blue}2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/34e1d57e4743c79dcc065e7f8d7e7582f5116f0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.687ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {blue}2}\cdot {\color {blue}2}\cdot {\color {blue}2}}" loading="lazy"></td>

<msup>

</mstyle>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}^{4}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/257c67552de8bc099199b294321f59575592d2f9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.217ex; height:2.676ex;" alt="{\displaystyle {\color {blue}2}^{4}}" loading="lazy">

</td></tr>

<tr>

<td>1

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 17}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c64120a0494859d76d7b9621af60dab553bd82dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 17}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 17}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c64120a0494859d76d7b9621af60dab553bd82dc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 17}" loading="lazy">

</td></tr>

<tr>

<td>3

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {darkgreen}3}\cdot {\color {darkgreen}3}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/11d3cefd241c17a411506b4bad2f1b36af552189.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.846ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {darkgreen}3}\cdot {\color {darkgreen}3}}" loading="lazy"></td>

</mstyle>

</mrow>

<msup>

</mstyle>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {darkgreen}3}^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7ce83fa20a7bb836807d2b3b66d59dc9a7a56170.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.058ex; height:2.676ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {darkgreen}3}^{2}}" loading="lazy">

</td></tr>

<tr>

<td>1

</td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 19}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d12e89044b8eb4a6034d16a39e9c9d0b5c2518ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 19}" loading="lazy"></td>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 19}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d12e89044b8eb4a6034d16a39e9c9d0b5c2518ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.325ex; height:2.176ex;" alt="{\displaystyle 19}" loading="lazy">

</td></tr>

<tr>

<td>3

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}\cdot {\color {blue}2}\cdot {\color {darkred}5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5559d0fd23a78656355fcc5df8389d367674c388.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:6.846ex; height:2.176ex;" alt="{\displaystyle {\color {blue}2}\cdot {\color {blue}2}\cdot {\color {darkred}5}}" loading="lazy"></td>

<msup>

</mstyle>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {blue}2}^{2}\cdot {\color {darkred}5}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/274dd5b8ef7713961f9c487328063f08168bb9e9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.058ex; height:2.676ex;" alt="{\displaystyle {\color {blue}2}^{2}\cdot {\color {darkred}5}}" loading="lazy">

</td></tr>

<tr>

<td>2

</td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkgreen}3}\cdot {\color {darkgray}7}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ce315c1fa6b6fcf2df177768aa5b7b0b9d06ce0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {darkgreen}3}\cdot {\color {darkgray}7}}" loading="lazy"></td>

</mstyle>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {darkgreen}3}\cdot {\color {darkgray}7}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ce315c1fa6b6fcf2df177768aa5b7b0b9d06ce0b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.004ex; height:2.176ex;" alt="{\displaystyle {\color {darkgreen}3}\cdot {\color {darkgray}7}}" loading="lazy">

</td></tr></tbody></table>

<div class="mw-heading mw-heading2"><h2 id="Definitionen">Definitionen</h2></div>

Sei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> eine natürliche Zahl. Eine Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> heißt Primfaktor von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">,

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> ein <a href="Teilbarkeit" title="Teilbarkeit">Teiler</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> ist und</li>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/81eac1e205430d1f40810df36a0edffdc367af36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:1.259ex; height:2.009ex;" alt="{\displaystyle p}" loading="lazy"> eine <a href="Primzahl" title="Primzahl">Primzahl</a> ist.</li></ul>

Die Primfaktorzerlegung ist die Darstellung der Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> als Produkt ihrer Primfaktoren. Da die <a href="Multiplikation" title="Multiplikation">Multiplikation</a> für <a href="Reelle_Zahl" title="Reelle Zahl">reelle Zahlen</a> <a href="Kommutativgesetz" title="Kommutativgesetz">kommutativ</a> und <a href="Assoziativgesetz" title="Assoziativgesetz">assoziativ</a> ist, ist die Reihenfolge der Primfaktoren aus Sicht der Zahlentheorie unwichtig. Die Primfaktorzerlegung der <a href="Eins" title="Eins">Eins</a> kann als <a href="Leeres_Produkt" title="Leeres Produkt">leeres Produkt</a> betrachtet werden. Wenn <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> selbst eine Primzahl ist, so ist sie selbst ihr einziger Primfaktor. Gibt es mehr als einen Primfaktor, so wird <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> als <a href="Zusammengesetzte_Zahl" title="Zusammengesetzte Zahl">zusammengesetzte Zahl</a> bezeichnet. <a href="Null" title="Null">Null</a> ist niemals Teil der <a href="Multiplikative_Gruppe" class="mw-redirect" title="Multiplikative Gruppe">multiplikativen Gruppe</a> und wird von solchen Betrachtungen ausgeschlossen. Ein Primfaktor kann mehrfach auftreten und daher muss in gewissen Kontexten die Zählweise (mit Vielfachheiten oder lediglich wie viele verschiedene) angegeben werden. Mehrfach auftretende Primfaktoren können mittels <a href="Potenz_(Mathematik)" title="Potenz (Mathematik)">Exponenten</a>schreibweise gut lesbar zusammengefasst werden. Sind die <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle M}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f82cade9898ced02fdd08712e5f0c0151758a0dd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.442ex; height:2.176ex;" alt="{\displaystyle M}" loading="lazy"> verschiedenen Primfaktoren <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1},\dots ,p_{M}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1},\dots ,p_{M}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f84b4c578af906407c014a8accf1fe172405cbfa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:10.62ex; height:2.009ex;" alt="{\displaystyle p_{1},\dots ,p_{M}}" loading="lazy"> aufsteigend <a href="Ordnungsrelation" title="Ordnungsrelation">geordnet</a> (<math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{k}<p_{k+1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{k}<p_{k+1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/42970f77ad162d0b7680e3d2a90d95acd43b7ceb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:9.805ex; height:2.176ex;" alt="{\displaystyle p_{k}<p_{k+1}}" loading="lazy">), spricht man auch von der kanonischen Primfaktorzerlegung:

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

</mrow>

</munderover>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\dotsm p_{M}^{e_{M}}=\prod _{k=1}^{M}p_{k}^{e_{k}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cdb00ccc015280e260a9b6df1fadbf949d1efadb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:28.885ex; height:7.343ex;" alt="{\displaystyle n=p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\dotsm p_{M}^{e_{M}}=\prod _{k=1}^{M}p_{k}^{e_{k}}}" loading="lazy"></dd></dl>

Der Exponent <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1a24f4c64db82ae2f1e89d9861304aec8598c7e5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.172ex; height:2.009ex;" alt="{\displaystyle e_{k}}" loading="lazy"> eines Primfaktors <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01084a31964201514f3e6bd0136989e11ea6e58a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.348ex; height:2.009ex;" alt="{\displaystyle p_{k}}" loading="lazy"> ist die Vielfachheit von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01084a31964201514f3e6bd0136989e11ea6e58a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.348ex; height:2.009ex;" alt="{\displaystyle p_{k}}" loading="lazy"> in <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> und wird auch als <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01084a31964201514f3e6bd0136989e11ea6e58a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.348ex; height:2.009ex;" alt="{\displaystyle p_{k}}" loading="lazy">-<a href="Bewertungstheorie" class="mw-redirect" title="Bewertungstheorie">Bewertung</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> bezeichnet. Er gibt an, wie oft <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> durch <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{k}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/01084a31964201514f3e6bd0136989e11ea6e58a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.348ex; height:2.009ex;" alt="{\displaystyle p_{k}}" loading="lazy"> teilbar ist. Mit Vielfachheit gezählt hat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> dann <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\textstyle N=e_{1}+\dots +e_{M}=\sum _{k=1}^{M}e_{k}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\textstyle N=e_{1}+\dots +e_{M}=\sum _{k=1}^{M}e_{k}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6568f0cd4f2b3500b31f678f037290306e7bfb87.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:30.047ex; height:3.509ex;" alt="{\textstyle N=e_{1}+\dots +e_{M}=\sum _{k=1}^{M}e_{k}}" loading="lazy"> Primfaktoren.

Eine äquivalente Schreibweise ist

</mrow>

</munder>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=\prod _{p\in \mathbb {P} }p^{e_{p}}~,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/22bf1c95796a3b83508d1c3f45fe0c4697014f70.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:12.081ex; height:5.843ex;" alt="{\displaystyle n=\prod _{p\in \mathbb {P} }p^{e_{p}}~,}" loading="lazy"></dd></dl>

wobei die Exponenten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e_{p}\in \mathbb {N} _{0}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{p}\in \mathbb {N} _{0}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eec8d5e6d790820f49cf9c3655dbd1eb4a393a4b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.716ex; height:2.843ex;" alt="{\displaystyle e_{p}\in \mathbb {N} _{0}}" loading="lazy"> nur für endlich viele <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\in \mathbb {P} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\in \mathbb {P} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7891a37dcb8b0ee507f9ef2038a853e245d76657.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.52ex; height:2.509ex;" alt="{\displaystyle p\in \mathbb {P} }" loading="lazy"> von 0 verschieden sind.

<div class="mw-heading mw-heading2"><h2 id="Beispiele_für_Primfaktorzerlegungen">Beispiele für Primfaktorzerlegungen</h2></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 30=2\cdot 3\cdot 5}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f22d72f6dff747c9b50f38af10fd12da9509f1f0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:12.269ex; height:2.176ex;" alt="{\displaystyle 30=2\cdot 3\cdot 5}" loading="lazy"></dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 37=37\ }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3f079cd8affc48ba0c577f23d1479eac3f0a4451.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.329ex; height:2.176ex;" alt="{\displaystyle 37=37\ }" loading="lazy"> (Primzahl)</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1001=7\cdot 11\cdot 13}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/80204281762091854e286cf9064eb48a9dcded31.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:16.919ex; height:2.176ex;" alt="{\displaystyle 1001=7\cdot 11\cdot 13}" loading="lazy"></dd>

<mrow>

</mrow>

</munder>

</mrow>

</mrow>

</munder>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1024=\underbrace {2\cdots 2} _{\text{10-mal}}=2^{10}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cd3e650c708cc8f9ed6924d38271443cb882100b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.671ex; width:19.708ex; height:6.009ex;" alt="{\displaystyle 1024=\underbrace {2\cdots 2} _{\text{10-mal}}=2^{10}}" loading="lazy"> (<a href="Zweierpotenz" class="mw-redirect" title="Zweierpotenz">Zweierpotenz</a>)</dd>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 6936=2\cdot 2\cdot 2\cdot 3\cdot 17\cdot 17}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/da6bea599ef41f05a1f27c7ed84902a13ee0659c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:25.443ex; height:2.176ex;" alt="{\displaystyle 6936=2\cdot 2\cdot 2\cdot 3\cdot 17\cdot 17}" loading="lazy">, mit der kanonischen Darstellung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{3}\cdot 3\cdot 17^{2}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{3}\cdot 3\cdot 17^{2}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/12f270fbba521f37e7814e1fa001ce6473e15995.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:10.117ex; height:2.676ex;" alt="{\displaystyle 2^{3}\cdot 3\cdot 17^{2}}" loading="lazy"></dd>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 10000=2^{4}\cdot 5^{4}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e315a002f2f5bd47596af105a89c53affa4df053.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:15.023ex; height:2.676ex;" alt="{\displaystyle 10000=2^{4}\cdot 5^{4}}" loading="lazy"> (<a href="Zehnerpotenz" title="Zehnerpotenz">Zehnerpotenz</a>)</dd></dl>

<div class="mw-heading mw-heading2"><h2 id="Fundamentalsatz_der_Arithmetik">Fundamentalsatz der Arithmetik</h2></div>

Die Aussagen für Existenz der Primfaktorzerlegung für jede natürliche Zahl und deren Eindeutigkeit in der kanonischen Darstellung sind der Fundamentalsatz der Arithmetik, auch Hauptsatz der elementaren Zahlentheorie genannt. Beide Aussagen werden getrennt formuliert und bewiesen. Die Beweise sind elementar, werden klassisch als <a href="Widerspruchsbeweis" class="mw-redirect" title="Widerspruchsbeweis">Widerspruchsbeweis</a> formuliert und nutzen die <a href="Wohlordnung" title="Wohlordnung">Wohlordnung</a> der natürlichen Zahlen. Zum ersten Mal vollständig und korrekt bewiesen findet sich der Fundamentalsatz der <a href="Arithmetik" title="Arithmetik">Arithmetik</a> in den <a href="Disquisitiones_Arithmeticae" title="Disquisitiones Arithmeticae">Disquisitiones Arithmeticae</a> von <a href="Carl_Friedrich_Gau%C3%9F" title="Carl Friedrich Gauß">Carl Friedrich Gauß</a>. Er war aber bereits – wenn auch in leicht abgewandelter Form – <a href="Euklid" title="Euklid">Euklid</a> bekannt.<a href="#cite_note-1">[1]</a>

<div class="mw-heading mw-heading3"><h3 id="Beweis_der_Existenz">Beweis der Existenz</h3></div>

Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/43611e9319bf4a85f6e9820e4ea0176471f6b2ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.681ex; height:2.176ex;" alt="{\displaystyle 0\in \mathbb {N} }" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fb0502207a46c563a3a19f1dcaac3bf83a906368.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.681ex; height:2.176ex;" alt="{\displaystyle 1\in \mathbb {N} }" loading="lazy"> ist nichts zu zeigen (vgl. <a href="Teilbarkeit#Definition" title="Teilbarkeit">Teilbarkeit</a>). Jede Primzahl ist selbst ihre Primfaktorzerlegung. Zu zeigen bleibt, dass für die restlichen natürlichen Zahlen eine Primfaktorzerlegung existiert.

Angenommen werde die Existenz solcher restlicher Zahlen, für die keine Primfaktorzerlegung existiert. Aufgrund der <a href="Wohlordnung" title="Wohlordnung">Wohlordnung</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdf9a96b565ea202d0f4322e9195613fb26a9bed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} }" loading="lazy"> existiert dann eine kleinste solche Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. Da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n>1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n>1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ee74e1cc07e7041edf0fcbd4481f5cd32ad17b64.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.656ex; height:2.176ex;" alt="{\displaystyle n>1}" loading="lazy"> keine Primzahl ist, hat <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nichttriviale <a href="Teilbarkeit" title="Teilbarkeit">Teiler</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a,b\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a,b\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b604733da4cfdd0d8c6c6956d592b26c2e1fc351.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.78ex; height:2.509ex;" alt="{\displaystyle a,b\in \mathbb {N} }" loading="lazy"> mit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a\cdot b=n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a\cdot b=n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0e5db5ca6fa239d0fbf253b9ce01da91d7eaa859.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.4ex; height:2.176ex;" alt="{\displaystyle a\cdot b=n}" loading="lazy">, wobei <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1<a,b<n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1<a,b<n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dbd7cc6b88714f80670809f640e0c9db7f17372a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.015ex; height:2.509ex;" alt="{\displaystyle 1<a,b<n}" loading="lazy">. Da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> die kleinste Zahl ist, für die keine Primfaktorzerlegung existiert, existiert für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ffd2487510aa438433a2579450ab2b3d557e5edc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.23ex; height:1.676ex;" alt="{\displaystyle a}" loading="lazy"> (bzw. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f11423fbb2e967f986e36804a8ae4271734917c3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.998ex; height:2.176ex;" alt="{\displaystyle b}" loading="lazy">) eine Primfaktorzerlegung <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a=\Pi p_{i}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a=\Pi p_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5599f5232e55976ab8cc45491b891c37d99f790.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.04ex; height:2.509ex;" alt="{\displaystyle a=\Pi p_{i}}" loading="lazy"> (bzw. <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b=\Pi q_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b=\Pi q_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/eba4377b0e21e5ab183197ca43cf870147d32f04.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.786ex; height:2.843ex;" alt="{\displaystyle b=\Pi q_{j}}" loading="lazy">). Dann ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pi p_{i}\cdot \Pi q_{j}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi p_{i}\cdot \Pi q_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7c49f15031ba6d1fb84fed6f67011f290b3dcbbb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:9.081ex; height:2.843ex;" alt="{\displaystyle \Pi p_{i}\cdot \Pi q_{j}}" loading="lazy"> eine Primfaktorzerlegung von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, im Widerspruch zur Annahme.

<div class="mw-heading mw-heading3"><h3 id="Beweis_der_Eindeutigkeit">Beweis der Eindeutigkeit</h3></div>

Für <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 0\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 0\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/43611e9319bf4a85f6e9820e4ea0176471f6b2ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.681ex; height:2.176ex;" alt="{\displaystyle 0\in \mathbb {N} }" loading="lazy">, <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1\in \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1\in \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fb0502207a46c563a3a19f1dcaac3bf83a906368.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.681ex; height:2.176ex;" alt="{\displaystyle 1\in \mathbb {N} }" loading="lazy"> und Primzahlen ist nichts zu zeigen. Zu zeigen bleibt, dass für die restlichen natürlichen Zahlen höchstens eine Primfaktorzerlegung existiert.

Angenommen werde die Existenz solcher restlicher Zahlen, für die jeweils mehrere unterschiedliche Primfaktorzerlegungen koexistieren. Aufgrund der <a href="Wohlordnung" title="Wohlordnung">Wohlordnung</a> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {N} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {N} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdf9a96b565ea202d0f4322e9195613fb26a9bed.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.678ex; height:2.176ex;" alt="{\displaystyle \mathbb {N} }" loading="lazy"> existiert dann eine kleinste solche Zahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">. Mehrere unterschiedliche Primfaktorzerlegungen von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> koexistieren höchstens dann (widerspruchsfrei), wenn zwei unterschiedliche Primfaktorzerlegungen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pi _{i=1}^{r}p_{i}}">

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi _{i=1}^{r}p_{i}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1f9ae17493c375b147aef9770393d708ff2cae4c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.612ex; height:2.843ex;" alt="{\displaystyle \Pi _{i=1}^{r}p_{i}}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \Pi _{j=1}^{s}q_{j}}">

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \Pi _{j=1}^{s}q_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b973bd24e7228b7472505e52db2532bab098af24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.338ex; width:6.7ex; height:3.176ex;" alt="{\displaystyle \Pi _{j=1}^{s}q_{j}}" loading="lazy"> von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> koexistieren. Außerdem ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nicht prim, also <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle r,s\geq 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle r,s\geq 2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8efb64235d8680a65fd4eef6c0ae424f18f51b33.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.434ex; height:2.509ex;" alt="{\displaystyle r,s\geq 2}" loading="lazy">.

Außerdem kann man <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{p_{1},\cdots ,p_{r}\}\cap \{q_{1},\cdots ,q_{s}\}=\emptyset }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{p_{1},\cdots ,p_{r}\}\cap \{q_{1},\cdots ,q_{s}\}=\emptyset }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/55940aab9aa27e7195373b123a97ccaa439dca7e.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.348ex; height:2.843ex;" alt="{\displaystyle \{p_{1},\cdots ,p_{r}\}\cap \{q_{1},\cdots ,q_{s}\}=\emptyset }" loading="lazy"> annehmen. Denn gäbe es einen gemeinsamen Faktor, nach Umsortierung zum Beispiel <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}=q_{1}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}=q_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/40f270ef3699fbf81cf218e62a71f45444f82bee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:7.503ex; height:2.009ex;" alt="{\displaystyle p_{1}=q_{1}}" loading="lazy">, so wäre <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\frac {n}{p_{1}}}<n}">

<mfrac>

<msub>

</mrow>

</msub>

</mfrac>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\frac {n}{p_{1}}}<n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dca961b8230e0c1624bb8b28973e3eb237219ab8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.338ex; width:7.553ex; height:5.176ex;" alt="{\displaystyle {\frac {n}{p_{1}}}<n}" loading="lazy">. Da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> minimale Zahl mit zwei verschiedenen Primfaktorzerlegungen ist, wäre <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{p_{2},\cdots ,p_{r}\}=\{q_{2},\cdots ,q_{s}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{p_{2},\cdots ,p_{r}\}=\{q_{2},\cdots ,q_{s}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b36c3cf8f16ad884dd3d5e533ed7c0c8ae4c859b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.603ex; height:2.843ex;" alt="{\displaystyle \{p_{2},\cdots ,p_{r}\}=\{q_{2},\cdots ,q_{s}\}}" loading="lazy">, und somit wären obige Primfaktorzerlegungen identisch. Ein Widerspruch zur Wahl von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">.

Da <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy"> das Produkt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n=\Pi q_{j}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=\Pi q_{j}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e26500155670120674c21346d5b9b62ceb303bce.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:8.183ex; height:2.843ex;" alt="{\displaystyle n=\Pi q_{j}}" loading="lazy"> teilt, teilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy"> nach dem <a href="Lemma_von_Euklid" title="Lemma von Euklid">Lemma von Euklid</a> auch einen geeignet gewählten Faktor dieses Produkts. Dies kann allerdings kein Primfaktor <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{q_{1},\cdots ,q_{s}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{q_{1},\cdots ,q_{s}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a1b4972f5105a37c81acab65cebdb052396753ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.635ex; height:2.843ex;" alt="{\displaystyle \{q_{1},\cdots ,q_{s}\}}" loading="lazy"> sein, denn sonst wäre <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}\in \{q_{1},\cdots ,q_{s}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}\in \{q_{1},\cdots ,q_{s}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/079172ee8b66bbd776ab75ff3a7be9af1e2ee091.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:16.789ex; height:2.843ex;" alt="{\displaystyle p_{1}\in \{q_{1},\cdots ,q_{s}\}}" loading="lazy">. Also teilt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy"> ein Produkt aus nur <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s-1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s-1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b027c8c033c9ca80d57161107c464eca1000e47f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.093ex; height:2.343ex;" alt="{\displaystyle s-1}" loading="lazy"> verschiedenen Elementen aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{q_{1},\cdots ,q_{s}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{q_{1},\cdots ,q_{s}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a1b4972f5105a37c81acab65cebdb052396753ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.635ex; height:2.843ex;" alt="{\displaystyle \{q_{1},\cdots ,q_{s}\}}" loading="lazy">. Dieses Argument kann man wiederholen, das heißt <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy"> teilt ein Produkt aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle s-2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle s-2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1594460591df3dd2ee9aa9315f9c18667c8b3ed7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.093ex; height:2.343ex;" alt="{\displaystyle s-2}" loading="lazy"> verschiedenen Elementen aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{q_{1},\cdots ,q_{s}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{q_{1},\cdots ,q_{s}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a1b4972f5105a37c81acab65cebdb052396753ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.635ex; height:2.843ex;" alt="{\displaystyle \{q_{1},\cdots ,q_{s}\}}" loading="lazy"> und so weiter. Schließlich muss <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b9b58f22283ca46dd5da309cc34303b06a797783.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:2.313ex; height:2.009ex;" alt="{\displaystyle p_{1}}" loading="lazy"> ein Element aus <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{q_{1},\cdots ,q_{s}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{q_{1},\cdots ,q_{s}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a1b4972f5105a37c81acab65cebdb052396753ca.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.635ex; height:2.843ex;" alt="{\displaystyle \{q_{1},\cdots ,q_{s}\}}" loading="lazy"> teilen. Da es sich um Primzahlen handelt, ist somit <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1}\in \{q_{1},\cdots ,q_{s}\}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1}\in \{q_{1},\cdots ,q_{s}\}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/079172ee8b66bbd776ab75ff3a7be9af1e2ee091.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; margin-left: -0.089ex; width:16.789ex; height:2.843ex;" alt="{\displaystyle p_{1}\in \{q_{1},\cdots ,q_{s}\}}" loading="lazy">. Dies ist ein Widerspruch.

<div class="mw-heading mw-heading2"><h2 id="Eigenschaften">Eigenschaften</h2></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> und <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n+1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n+1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2a135e65a42f2d73cccbfc4569523996ca0036f1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.398ex; height:2.343ex;" alt="{\displaystyle n+1}" loading="lazy"> können <a href="Teilerfremdheit" title="Teilerfremdheit">keine gemeinsamen Primfaktoren</a> haben.</li>

<li>Um die Primfaktorzerlegung einer Zahl zu berechnen, stehen mehrere <a href="Faktorisierungsverfahren" title="Faktorisierungsverfahren">Faktorisierungsverfahren</a> zur Verfügung, die <a href="Nichttrivialer_Teiler" class="mw-redirect" title="Nichttrivialer Teiler">nichttriviale Teiler</a> ganzer Zahlen berechnen. Diese Aufgabenstellung ist als <a href="Faktorisierungsproblem_f%C3%BCr_ganze_Zahlen" class="mw-redirect" title="Faktorisierungsproblem für ganze Zahlen">Faktorisierungsproblem für ganze Zahlen</a> bekannt und kann mit den bisher bekannten Methoden nicht <a href="Effizienz_(Informatik)" title="Effizienz (Informatik)">effizient</a> berechnet werden, worauf weltweit Sicherheitskonzepte beruhen, insbesondere in der modernen <a href="Kryptographie" title="Kryptographie">Kryptographie</a>. Siehe auch <a href="Primzahltest" title="Primzahltest">Primzahltest</a>.</li>

<li><a href="Godfrey_Harold_Hardy" title="Godfrey Harold Hardy">Hardy</a> bewies mehrere erstaunliche <a href="Statistik" title="Statistik">statistische</a> Erkenntnisse zum Thema, unter anderem, dass die durchschnittliche Anzahl von Primfaktoren für größer werdendes <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"> nur sehr langsam anwächst und zwar wie <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ln(\ln(n))}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ln(\ln(n))}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ae120bf0c67b4e5c8fe4fd54a8c3e788f0d60e74.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:8.892ex; height:2.843ex;" alt="{\displaystyle \ln(\ln(n))}" loading="lazy">, also der doppelt angewendete <a href="Nat%C3%BCrlicher_Logarithmus" class="mw-redirect" title="Natürlicher Logarithmus">natürliche Logarithmus</a>. Der <a href="Satz_von_Erd%C5%91s-Kac" title="Satz von Erdős-Kac">Satz von Erdős-Kac</a> besagt darüber hinaus, dass die Anzahl der Primfaktoren <a href="Normalverteilung" title="Normalverteilung">asymptotisch normalverteilt</a> ist mit einem <a href="Erwartungswert" title="Erwartungswert">Erwartungswert</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \ln \ln n+{\mathcal {O}}(1)}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \ln \ln n+{\mathcal {O}}(1)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/940cd403dab5e4e735f1852096d5b26ef9f1feb1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.71ex; height:2.843ex;" alt="{\displaystyle \ln \ln n+{\mathcal {O}}(1)}" loading="lazy"> und einer <a href="Standardabweichung_(Wahrscheinlichkeitstheorie)" class="mw-redirect" title="Standardabweichung (Wahrscheinlichkeitstheorie)">Standardabweichung</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\mathcal {O}}({\sqrt {\ln \ln n}})}">

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\mathcal {O}}({\sqrt {\ln \ln n}})}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b22b244a710e1178fdbc6bd3df3d25154c711e89.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.643ex; height:3.176ex;" alt="{\displaystyle {\mathcal {O}}({\sqrt {\ln \ln n}})}" loading="lazy">.<a href="#cite_note-2">[2]</a> (Zur Notation siehe <a href="Landau-Symbole" title="Landau-Symbole">Landau-Symbole</a>.)</li>

<li>Die Funktion <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega (n)}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega (n)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f9e1e190faf1ba7931e4e98594df6097d297bed1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.65ex; height:2.843ex;" alt="{\displaystyle \omega (n)}" loading="lazy">, die jede natürliche Zahl auf die Anzahl ihrer <a href="Paarweise_verschieden" title="Paarweise verschieden">paarweise verschiedenen</a> Primfaktoren abbildet, ist ein Beispiel für eine <a href="Zahlentheoretische_Funktion" title="Zahlentheoretische Funktion">arithmetische Funktion</a>, die <a href="Additivit%C3%A4t#Definition_in_der_Zahlentheorie" class="mw-redirect" title="Additivität">additiv aber nicht streng additiv</a> ist. Sie ist zu unterscheiden von der <a href="Teileranzahlfunktion" title="Teileranzahlfunktion">Teileranzahlfunktion</a>, die alle Teiler einer Zahl zählt, nicht nur die Primteiler. Beispielsweise ist <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega (1000)=2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega (1000)=2}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/62ffa8bcaf0ddc19c623b0984dd731d0dac67798.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:12.166ex; height:2.843ex;" alt="{\displaystyle \omega (1000)=2}" loading="lazy">, denn die Primfaktorzerlegung enthält zwei verschiedene Primzahlen: 2 und 5. Mit <a href="#Definitionen">obiger</a> Definition gilt: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \omega (n)=M}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \omega (n)=M}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a97b8fb925700b00df27d337a238483e92065c8b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:10.19ex; height:2.843ex;" alt="{\displaystyle \omega (n)=M}" loading="lazy">.</li>

<li>Der asymptotische <a href="Arithmetischer_Mittelwert" class="mw-redirect" title="Arithmetischer Mittelwert">arithmetische Mittelwert</a> der maximalen Exponenten der Primfaktorzerlegungen der Zahlen 1, 2, 3, … ist die <a href="Niven-Konstante" title="Niven-Konstante">Niven-Konstante</a> (rund 1,7), der asymptotische arithmetische Mittelwert der minimalen Exponenten ist genau 1.</li>

<li>Der asymptotische Erwartungswert der relativen Anzahl der Ziffern des größten Primfaktors einer Zahl wird durch die <a href="Golomb-Dickman-Konstante" title="Golomb-Dickman-Konstante">Golomb-Dickman-Konstante</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \gamma \approx 0{,}62433}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \gamma \approx 0{,}62433}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5d33ccc51cbe778c3915293be504e93e67fa39e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:11.982ex; height:2.676ex;" alt="{\displaystyle \gamma \approx 0{,}62433}" loading="lazy"> angegeben.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Verallgemeinerung">Verallgemeinerung</h2></div>

Es gibt mehrere Möglichkeiten, Primzahlen zu verallgemeinern. Die bekannteste Anwendung sind die <a href="Ganze_Zahl" title="Ganze Zahl">ganzen Zahlen</a>, Primzahlen können dort auch ein negatives <a href="Vorzeichen_(Zahl)" title="Vorzeichen (Zahl)">Vorzeichen</a> haben. Andererseits ist dies schon ein spezielles Beispiel, da auch dort die Primfaktorzerlegung (bis auf Vorzeichen und Reihenfolge) eindeutig ist.

Genauso eindeutig ist die Primfaktorzerlegung in den von 0 verschiedenen rationalen Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q\in \mathbb {Q} ^{\times }}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q\in \mathbb {Q} ^{\times }}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fe745c283fa0fd3893d9250e55483294a59f9385.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:7.229ex; height:2.676ex;" alt="{\displaystyle q\in \mathbb {Q} ^{\times }}" loading="lazy">

</mrow>

</munder>

<msup>

<msub>

</mrow>

</msub>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q=\pm \prod _{p\in \mathbb {P} }p^{e_{p}}~,}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/692de933cd8464359fd5f1de845e1b1bf271236d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.338ex; width:13.951ex; height:5.843ex;" alt="{\displaystyle q=\pm \prod _{p\in \mathbb {P} }p^{e_{p}}~,}" loading="lazy"></dd></dl>

wobei die ganzzahligen Exponenten <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e_{p}\in \mathbb {Z} }">

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{p}\in \mathbb {Z} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/fdabb533cda6d29ffddb4d41773b2f393d4313bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:6.534ex; height:2.843ex;" alt="{\displaystyle e_{p}\in \mathbb {Z} }" loading="lazy"> nur für endlich viele <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p\in \mathbb {P} }">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p\in \mathbb {P} }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7891a37dcb8b0ee507f9ef2038a853e245d76657.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:5.52ex; height:2.509ex;" alt="{\displaystyle p\in \mathbb {P} }" loading="lazy"> von 0 verschieden sind.

Ein allgemeiner Ansatz verlangt mindestens einen Begriff der Teilbarkeit innerhalb der mathematischen Struktur. <a href="David_Hilbert" title="David Hilbert">David Hilbert</a> bewies, dass für die gewünschte Eindeutigkeit eine <a href="Addition" title="Addition">additive Struktur</a> zwingend notwendig ist. Üblicherweise wird von einem kommutativen <a href="Ring_mit_Eins" class="mw-redirect" title="Ring mit Eins">Ring mit Eins</a> ausgegangen, dort können <a href="Primelement" title="Primelement">Primelemente</a> definiert werden: Ein Element ist prim, wenn <a href="Lemma_von_Euklid" title="Lemma von Euklid">Euklids Lemma</a> dafür gilt. Damit ist nicht garantiert, dass es für alle Elemente des Rings Zerlegungen in Primelemente gibt, aber wenn es welche gibt, dann sind sie eindeutig. Um die Existenz zu sichern, ist eine weitere Eigenschaft notwendig: die Unzerlegbarkeit. Um die definieren zu können, schränkt man die Struktur weiter ein und betrachtet <a href="Nullteiler" title="Nullteiler">nullteilerfreie</a> Ringe (also <a href="Integrit%C3%A4tsring" title="Integritätsring">Integritätsringe</a>), dort können zusätzlich <a href="Irreduzibles_Element" class="mw-redirect" title="Irreduzibles Element">irreduzible Elemente</a> definiert werden, die aber nicht prim genannt werden können. Sie sind unzerlegbar und enthalten die Primelemente als <a href="Teilmenge" title="Teilmenge">Teilmenge</a>.

Zerlegungen in irreduzible Elemente in einem Integritätsring sind nicht notwendigerweise eindeutig. Um eine Struktur zu erhalten, in der die Produkt-Zerlegungen eindeutig sind, muss man diese Eindeutigkeit explizit fordern, was zur Definition von <a href="Faktorieller_Ring" title="Faktorieller Ring">faktoriellen Ringen</a> führt. Mit dieser Forderung lässt sich dann aber dort auch schon die Äquivalenz von irreduzibel und prim folgern: Faktorielle Ringe sind <a href="ZPE-Ring" class="mw-redirect" title="ZPE-Ring">ZPE-Ringe</a>. Ein etwas anderer Ansatz wird mit <a href="Primideal" title="Primideal">Primidealen</a> verfolgt.

<div class="mw-heading mw-heading3"><h3 id="Beispiele">Beispiele</h3></div>

<ul><li>In dem Integritätsring <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}">

</mrow>

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a37499ef27234d8a67a65932184280bb17301312.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:7.75ex; height:3.009ex;" alt="{\displaystyle \mathbb {Z} [{\sqrt {-5}}]}" loading="lazy"> sind die Elemente <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2,3,1\pm {\sqrt {-5}}}">

<msqrt>

</msqrt>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2,3,1\pm {\sqrt {-5}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/435c637a0894513b8ddfa4e77eef2493199ce8da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.302ex; height:3.009ex;" alt="{\displaystyle 2,3,1\pm {\sqrt {-5}}}" loading="lazy"> keine Primelemente aber irreduzibel, und keine zwei sind zueinander <a href="Assoziierte_Elemente" title="Assoziierte Elemente">assoziiert</a>. Es gilt: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 6=2\cdot 3=\left(1+{\sqrt {-5}}\right)\cdot \left(1-{\sqrt {-5}}\right)}">

<mrow>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

<mrow>

<mrow>

<msqrt>

</msqrt>

</mrow>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 6=2\cdot 3=\left(1+{\sqrt {-5}}\right)\cdot \left(1-{\sqrt {-5}}\right)}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bfb92114ec48ee4318c071cf034cae9c104e5f27.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:35.121ex; height:3.176ex;" alt="{\displaystyle 6=2\cdot 3=\left(1+{\sqrt {-5}}\right)\cdot \left(1-{\sqrt {-5}}\right)}" loading="lazy">. Man kann also nicht von einer Primfaktorzerlegung sprechen.</li>

<li>Ein <a href="Irreduzibles_Polynom" title="Irreduzibles Polynom">irreduzibles Polynom</a> heißt <a href="Primpolynom" class="mw-redirect" title="Primpolynom">Primpolynom</a>, wenn der <a href="Leitkoeffizient" class="mw-redirect" title="Leitkoeffizient">Leitkoeffizient</a> gleich <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 1}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/92d98b82a3778f043108d4e20960a9193df57cbf.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.162ex; height:2.176ex;" alt="{\displaystyle 1}" loading="lazy"> ist. Im <a href="Polynomring" title="Polynomring">Polynomring</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K[x]}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K[x]}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8a9e6c2ac2830d6a9abe078b47450777c41d69a9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:4.689ex; height:2.843ex;" alt="{\displaystyle K[x]}" loading="lazy"> über einem <a href="K%C3%B6rper_(Algebra)" title="Körper (Algebra)">Körper</a> <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle K}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle K}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2b76fce82a62ed5461908f0dc8f037de4e3686b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.066ex; height:2.176ex;" alt="{\displaystyle K}" loading="lazy"> ist jedes nichtkonstante <a href="Polynom" title="Polynom">Polynom</a> im Wesentlichen eindeutig als Produkt von Primpolynomen darstellbar.<a href="#cite_note-3">[3]</a></li>

<li>Sowohl in den <a href="Gau%C3%9Fsche_Zahl" title="Gaußsche Zahl">gaußschen Zahlen</a> als auch den <a href="Eisenstein-Zahl" title="Eisenstein-Zahl">Eisenstein-Zahlen</a> existiert stets eine Primfaktorzerlegung (außer für die 0).</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Praktische_Anwendung">Praktische Anwendung</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Teiler">Teiler</h3></div>

Aus den Primfaktorzerlegungen zweier Zahlen lässt sich erkennen, ob die eine Zahl durch die andere teilbar ist.

Das kleinste gemeinsame Vielfache (<a href="KgV" class="mw-redirect" title="KgV">kgV</a>) und der größte gemeinsame Teiler (<a href="GgT" class="mw-redirect" title="GgT">ggT</a>) können leicht aus den Primfaktorzerlegungen bestimmt werden. In der <a href="Bruchrechnung" title="Bruchrechnung">Bruchrechnung</a> können Brüche durch den ggT von Zähler und Nenner gekürzt werden. Beim Addieren und Subtrahieren werden zwei Brüche auf das kgV der Nenner erweitert.

Aus der kanonischen Primfaktorzerlegung

</mrow>

</mrow>

</munderover>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n=\prod _{k=1}^{M}p_{k}^{\;\;e_{k}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f4755fb4d87bd5dbc0039c2d02edd57221e629a8.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:12.167ex; height:7.343ex;" alt="{\displaystyle n=\prod _{k=1}^{M}p_{k}^{\;\;e_{k}}}" loading="lazy"></dd></dl>

erhält man die Anzahl <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle T}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ec7200acd984a1d3a3d7dc455e262fbe54f7f6e0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.636ex; height:2.176ex;" alt="{\displaystyle T}" loading="lazy"> der Teiler von <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy">, indem man die Exponenten um Eins erhöht und dann miteinander multipliziert:

</mrow>

</mrow>

</munderover>

<msub>

</mrow>

</msub>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle T=\prod _{k=1}^{M}{(e_{k}+1)}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/15c4dc7fef84f48d43d680f3c487da09530c84d4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.005ex; width:16.076ex; height:7.343ex;" alt="{\displaystyle T=\prod _{k=1}^{M}{(e_{k}+1)}}" loading="lazy"></dd></dl>

<div class="mw-heading mw-heading3"><h3 id="Kryptographie">Kryptographie</h3></div>

Eine wichtige Rolle spielen Primzahlen in der <a href="Kryptographie" title="Kryptographie">Kryptographie</a>. Verschlüsselungssysteme wie <a href="RSA-Kryptosystem" title="RSA-Kryptosystem">RSA</a> basieren darauf, dass kein effizientes <a href="Faktorisierungsverfahren" title="Faktorisierungsverfahren">Faktorisierungsverfahren</a> bekannt ist. So ist es innerhalb von Sekunden problemlos möglich, zwei 500-stellige Primzahlen zu finden und miteinander zu multiplizieren. Mit den heutigen Methoden würde die Rückgewinnung der beiden Primfaktoren aus diesem 999- oder 1000-stelligen Produkt dagegen eine sehr lange Zeit dauern.

<div class="mw-heading mw-heading3"><h3 id="Gödelnummern">Gödelnummern</h3></div>

Für jede Aufzählung von Primzahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle p_{1},p_{2},\ldots }">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle p_{1},p_{2},\ldots }</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5d2a5f0df47b52b649e76beb97452539b7c058b0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; margin-left: -0.089ex; width:9.328ex; height:2.009ex;" alt="{\displaystyle p_{1},p_{2},\ldots }" loading="lazy"> ohne Wiederholung ist die durch

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mrow>

<msub>

</mrow>

</msub>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (e_{1},e_{2},\ldots ,e_{M})\mapsto p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\dotsm p_{M}^{e_{M}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/83456ecd505c69dca4f87807e1b9d68371bb64ee.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:33.863ex; height:3.176ex;" alt="{\displaystyle (e_{1},e_{2},\ldots ,e_{M})\mapsto p_{1}^{e_{1}}\cdot p_{2}^{e_{2}}\dotsm p_{M}^{e_{M}}}" loading="lazy"></dd></dl>

definierte Abbildung aller <a href="Tupel" title="Tupel">Tupel</a> ganzer Zahlen <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle e_{1},e_{2},\ldots ,e_{M-1}\geq 0,\ e_{M}>0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle e_{1},e_{2},\ldots ,e_{M-1}\geq 0,\ e_{M}>0}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/328639704d0f99104e974cc8db8a485a08376bd0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:28.81ex; height:2.509ex;" alt="{\displaystyle e_{1},e_{2},\ldots ,e_{M-1}\geq 0,\ e_{M}>0}" loading="lazy"> <a href="Injektive_Funktion" title="Injektive Funktion">injektiv</a> und berechenbar, durch Primfaktorzerlegung ist die <a href="Umkehrfunktion" title="Umkehrfunktion">Umkehrfunktion</a> ebenfalls berechenbar. Die Abbildung eignet sich daher zur Definition von <a href="G%C3%B6delnummer" title="Gödelnummer">Gödelnummern</a>.

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li>Jürgen Wolfart: <cite style="font-style:italic">Einführung in die Algebra und Zahlentheorie</cite>. Vieweg, Braunschweig/Wiesbaden 1996, ISBN 3-528-07286-5.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Primfaktorzerlegung&rft.au=J%C3%BCrgen+Wolfart&rft.btitle=Einf%C3%BChrung+in+die+Algebra+und+Zahlentheorie&rft.date=1996&rft.genre=book&rft.isbn=3528072865&rft.place=Braunschweig%2FWiesbaden&rft.pub=Vieweg" style="display:none"> </li></ul>

<div class="mw-heading mw-heading2"><h2 id="Weblinks">Weblinks</h2></div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><div class="noviewer" style="display:inline-block; line-height:10px; min-width:1.6em; text-align:center;" aria-hidden="true" role="presentation"></div><a href="https://de.wikibooks.org/wiki/Mathematrix:_Kompass/_Grundrechenarten_und_Bruchrechnungen/_Primfaktorzerlegung" class="extiw external" title="b:Mathematrix: Kompass/ Grundrechenarten und Bruchrechnungen/ Primfaktorzerlegung">Wikibooks: <math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle {\color {BlueViolet}{\begin{matrix}{\mathbf {MATHE} \mu \alpha T\mathbb {R} ix}\end{matrix}}}}">

<mtr>

<mtd>

</mrow>

</mrow>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\color {BlueViolet}{\begin{matrix}{\mathbf {MATHE} \mu \alpha T\mathbb {R} ix}\end{matrix}}}}</annotation>

</semantics>

</math><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/648b8f837ba17ef3e5a90e6a86b41956ecba9422.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:19.352ex; height:2.843ex;" alt="{\displaystyle {\color {BlueViolet}{\begin{matrix}{\mathbf {MATHE} \mu \alpha T\mathbb {R} ix}\end{matrix}}}}" loading="lazy"> Mathematik für die Schule</a> – Primfaktorzerlegung</div>

<div class="sisterproject" style="margin:0.1em 0 0 0;"><a href="https://de.wiktionary.org/wiki/Primfaktorzerlegung" class="extiw external" title="wikt:Primfaktorzerlegung">Wiktionary: Primfaktorzerlegung</a> – Bedeutungserklärungen, Wortherkunft, Synonyme, Übersetzungen</div>

<ul><li><a rel="nofollow" class="external text" href="http://factordb.com/index.php">Factorization database von Markus Tervooren</a> – schnelle Verarbeitung, bis zu 200.000 Dezimalstellen</li>

<li><a rel="nofollow" class="external text" href="https://www.arndt-bruenner.de/mathe/scripts/primzahlen.htm">Die Primzahlseite</a> von Arndt Brünner – benötigt <a href="JavaScript" title="JavaScript">JavaScript</a>, enthält u. a. Primfaktorzerlegung</li>

<li><a rel="nofollow" class="external text" href="https://www.alpertron.com.ar/ECM.HTM">Factorization using the Elliptic Curve Method</a> – <a href="Java-Applet" title="Java-Applet">Java-Applet</a>, verarbeitet Eingaben bis 10.000 Dezimalstellen</li>

<li>Video: <a rel="nofollow" class="external text" href="https://av.tib.eu/media/19878">Primfaktorzerlegung</a>. <a href="P%C3%A4dagogische_Hochschule_Heidelberg" title="Pädagogische Hochschule Heidelberg">Pädagogische Hochschule Heidelberg</a> (PHHD) 2012, zur Verfügung gestellt von der <a href="Technische_Informationsbibliothek" class="mw-redirect" title="Technische Informationsbibliothek">Technischen Informationsbibliothek</a> (TIB), <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.5446/19878">10.5446/19878</a>.</li>

<li>Video: <a rel="nofollow" class="external text" href="https://av.tib.eu/media/19874">Der Hauptsatz der elementaren Zahlentheorie (Teil 1)</a>. <a href="P%C3%A4dagogische_Hochschule_Heidelberg" title="Pädagogische Hochschule Heidelberg">Pädagogische Hochschule Heidelberg</a> (PHHD) 2012, zur Verfügung gestellt von der <a href="Technische_Informationsbibliothek" class="mw-redirect" title="Technische Informationsbibliothek">Technischen Informationsbibliothek</a> (TIB), <a href="Digital_Object_Identifier" title="Digital Object Identifier">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.5446/19874">10.5446/19874</a>.</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><a href="#cite_ref-1">↑</a> Franz Lemmermeyer: <a rel="nofollow" class="external text" href="https://www.mathi.uni-heidelberg.de/~flemmermeyer/publ/euk-1.pdf">Zur Zahlentheorie der Griechen</a> (PDF; 208 kB)

</li>

<li id="cite_note-2"><a href="#cite_ref-2">↑</a> Thomas Kantke: <cite style="font-style:italic">Billige und teure Zahlen</cite>. In: <cite style="font-style:italic"><a href="Spektrum_der_Wissenschaft" title="Spektrum der Wissenschaft">Spektrum der Wissenschaft</a> – SPEZIAL: Omega</cite>. Nr. 4/2003. Spektrum der Wissenschaft, Heidelberg 2003, S. 68–74.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Primfaktorzerlegung&rft.atitle=Billige+und+teure+Zahlen&rft.au=Thomas+Kantke&rft.date=2003&rft.genre=journal&rft.issue=4%2F2003&rft.jtitle=Spektrum+der+Wissenschaft+-+SPEZIAL%3A+Omega&rft.pages=68-74&rft.place=Heidelberg&rft.pub=Spektrum+der+Wissenschaft" style="display:none">

</li>

<li id="cite_note-3"><a href="#cite_ref-3">↑</a> Jürgen Wolfart: <cite style="font-style:italic">Einführung in die Algebra und Zahlentheorie</cite>. Vieweg, Braunschweig/Wiesbaden 1996, ISBN 3-528-07286-5, S. 72, 37.<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Abook&rfr_id=info:sid/de.wikipedia.org:Primfaktorzerlegung&rft.au=J%C3%BCrgen+Wolfart&rft.btitle=Einf%C3%BChrung+in+die+Algebra+und+Zahlentheorie&rft.date=1996&rft.genre=book&rft.isbn=3528072865&rft.pages=72%2C+37&rft.place=Braunschweig%2FWiesbaden&rft.pub=Vieweg" style="display:none">

</li>

</ol>

<div>

Normdaten (Sachbegriff): <a href="Gemeinsame_Normdatei" title="Gemeinsame Normdatei">GND</a>: <a rel="nofollow" class="external text" href="https://d-nb.info/gnd/4175717-8">4175717-8</a> </div>

</div></div></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2026-01-06" href="https://de.wikipedia.org/wiki/?title=Primfaktorzerlegung&oldid=263097221">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>